package traverse

import "../binarytree"

type TreeNode = binarytree.TreeNode

func postOrder(root *TreeNode) []int {
	var res []int
	helper(root,&res)
	return res
}
func helper(root *TreeNode, res *[]int) {
	if root !=nil {
		helper(root.Left,res)
		helper(root.Right, res)
		*res = append(*res,root.Val)
	}
}


// 迭代版本的后序遍历   左右中
// 实现思路：先序调整（中左右）-> 中右左 -> 调转左右中
func postOrderNon(root *TreeNode) []int {
	if root == nil {
		return nil
	}
	// 使用栈
	stack := []*TreeNode{root}
	var res []int

	for len(stack) > 0 {
		// 访问
		curNode := stack[len(stack)-1]
		stack = stack[:len(stack)-1] //出栈操作
		res = append(res, curNode.Val)
		if curNode.Left != nil {
			stack = append(stack, curNode.Left)
		}
		if curNode.Right != nil {
			stack = append(stack, curNode.Right)
		}
	}
	// 逆序
	reverseArr(res) 
	return res
}
func reverseArr(a []int) {
	n := len(a)
	for i:=0;i<n/2;i++{
		a[i],a[n-i-1] = a[n-i-1],a[i]
	}
}